#include "Polygon.h"
#include <cmath>
#ifdef _TEST
#include <iostream>
#include <cstdio>
#endif
#ifdef _TEST_PERF
#include <gperftools/profiler.h>
#endif
using namespace std;

double Node::min[2], Node::max[2];
map<int, Node*> Node::m;
map<int, Polygon*> Polygon::m;
int count = 0;

RTree<Node*, double, 2, double, MAXNODES> pointTree;
RTree<Polygon*, double, 2, double, MAXNODES> polygonTree; // [MAXTREES];

vector<int> ans;
bool sum;

// 判断 x 在区间 a b 内
inline bool xInInterval(double x, double a, double b)
{ return fabs(x - a) < 1.e-8 || fabs(x - b) < 1.e-8 || (a < x && x < b) || (b < x && x < a); }

// 判断线段 p1 p2 与 y 处从 x 开始沿 x 轴正方向的射线是否有交点
bool judgePos(double x, double y, pair<double, double> &p1, pair<double, double> &p2)
{
	if (fabs(p1.second - p2.second) < 1.e-8)	// 线段平行于 x 轴
		return 0;
		// return (fabs(p1.second - y) < 1.e-8) ? 2 : 0;
	if (fabs(p1.first - p2.first) < 1.e-8)		// 线段平行于 y 轴
		return  xInInterval(y, p1.second, p2.second) && (fabs(x - p1.first) < 1.e-8 || x < p1.first) ? 1 : 0;
	double xx = ((p2.second - y) * p1.first - (p1.second - y) * p2.first) / (p2.second - p1.second);	// 线段所在直线与直线 y = y 交点横座标
#ifdef _TEST
	printf("(x, y) = (%lf, %lf)\n", x, y);
	printf("p1(%lf, %lf) p2(%lf, %lf)\n", p1.first, p1.second, p2.first, p2.second);
	printf("xx = %lf\n", xx);
#endif
	return fabs(xx - x) < 1.e-8 || (xInInterval(xx, p1.first, p2.first) && xx > x) ? 1 : 0;
}

// 射线法判断点是否在多边形内
bool pointInPolygon(double x, double y, Polygon &pol)
{
	sum = false;
	double *tmp = new double[4];
	tmp[0] = x;
	tmp[1] = tmp[3] = y;
	tmp[2] = 1.e32;
	pol.edge.Search(tmp, tmp + 2, edgeSearchCallback, tmp);
	delete []tmp;
	return sum;
}

// 构造多边形，将所有的边信息存储在 RTree 中，同时计算出多边形的外接矩形
Polygon::Polygon(int id, vector< pair<double, double> > &pt): id(id) // , tpos(count)
{
	auto i = pt.begin(), j = pt.end(), k = j;
	double max1, max2, min1, min2, *tmp;
	bool  posFlag;	// 判断边在矩形中的位置是“正向”还是“反向”
	max1 = min1 = i->first;
	max2 = min2 = i->second;
	for (; i != j; i++)
	{
		if (i->first > max1)
			max1 = i->first;
		else
			if (i->first < min1)
				min1= i->first;
		if (i->second > max2)
			max2 = i->second;
		else
			if (i->second < min2)
				min2= i->second;

		// 将每条边存储到 R-树中
		if (i + 1 != j)
			k = i + 1;
		else
			k = pt.begin();
		tmp = new double[4];
		posFlag = false;
		if (i->first > k->first)
		{
			posFlag = !posFlag;
			tmp[0] = k->first;
			tmp[2] = i->first;
		}
		else
		{
			tmp[2] = k->first;
			tmp[0] = i->first;
		}
		if (i->second > k->second)
		{
			posFlag = !posFlag;
			tmp[1] = k->second;
			tmp[3] = i->second;
		}
		else
		{
			tmp[3] = k->second;
			tmp[1] = i->second;
		}
		edge.Insert(tmp, tmp + 2, new pair<double *, bool>(tmp, posFlag));
	}

	Polygon::max[0] = max1, Polygon::min[0] = min1;
	Polygon::max[1] = max2, Polygon::min[1] = min2;
}

// 在存放点的 RTree 中找到范围内的叶节点，判断是否在多边形内
bool pointSearchCallback(Node *ndptr, void *arg)
{
	Polygon *ptr = (Polygon *)arg;
	if (pointInPolygon(ndptr->x, ndptr->y, *ptr))
		ans.push_back(ndptr->id);
	return true;
}

// 在存放多边形的 RTree 中找到包含点的叶节点，判断点是否在多边形内
bool polygonSearchCallback(Polygon *polptr, void *arg)
{
	double *ptr = (double *)arg;
	if (pointInPolygon(ptr[0], ptr[1], *polptr))
		ans.push_back(polptr->id);
	return true;
}

// 在多边形存储边信息的 RTree 中找到和射线相交的线段区域，判断线段是否和射线相交
// dt 提供边的所有信息
// arg 提供点的位置信息
bool edgeSearchCallback(pair<double *, bool> *dt, void *arg)
{
	double *point = (double *) arg;
	double *edge = dt->first;
	pair<double, double> edge1, edge2;
	if (dt->second)
	{
		edge1.first = edge[0];
		edge1.second = edge[3];
		edge2.first = edge[2];
		edge2.second = edge[1];
	}
	else
	{
		edge1.first = edge[0];
		edge1.second = edge[1];
		edge2.first = edge[2];
		edge2.second = edge[3];
	}
#ifdef _TEST
	cout << "edgeSearchCallback:" << endl
		<< "origin:" << dt->second << endl
		<< edge[0] << ' ' << edge[1] << ' ' << edge[2] << ' ' << edge[3] << endl
		<< edge1.first << ' ' << edge1.second << endl
		<< edge2.first << ' ' << edge2.second << endl;
#endif
	sum ^= judgePos(point[0], point[1], edge1, edge2);
	return true;
}

/*
 * 以下全部为 六个 commit 中调用的程序
 *
 */

void AddPolygon(int id, int n, vector<pair<double, double>> &polygon) {
	Polygon *polptr = new Polygon(id, polygon);
	Polygon::m.insert(make_pair(id, polptr));
	polygonTree.Insert(polptr->min, polptr->max, polptr);
	// polygonTree[count].Insert(polptr->min, polptr->max, polptr);
	// count = (count + 1) % MAXTREES;
}

void DeletePolygon(int id) {
	Polygon *polptr = Polygon::m[id];
	if (polptr)
	{
		// polygonTree[polptr->tpos].Remove(polptr->min, polptr->max, polptr);
		polygonTree.Remove(polptr->min, polptr->max, polptr);
		delete polptr;
	}
	Polygon::m.erase(id);
}

vector<int> QueryPolygon(int n, vector<pair<double, double>> &polygon) {
#ifdef _TEST_PERF
	ProfilerStart("QueryPolygon");
#endif
	ans.clear();
	Polygon* polptr = new Polygon(0, polygon);
	pointTree.Search(polptr->min, polptr->max, pointSearchCallback, polptr);
#ifdef _SORT_ENABLE_
	sort(ans.begin(), ans.end());
#endif
#ifdef _TEST_PERF
	ProfilerStop();
#endif
    return ans;
}

void AddPoint(int id, double x, double y) {
	Node *ndptr = new Node(id, x, y);
	Node::m.insert(make_pair(id, ndptr));
	Node::setRec(x, y);
	pointTree.Insert(Node::min, Node::max, ndptr);
}

void DeletePoint(int id) {
	Node *ndptr = Node::m[id];
	if (ndptr)
	{
		Node::setRec(ndptr->x, ndptr->y);
		pointTree.Remove(Node::min, Node::max, ndptr);
		delete ndptr;
	}
	Node::m.erase(id);
}

vector<int> QueryPoint(double x, double y) {
#ifdef _TEST_PERF
	ProfilerStart("QueryPoint");
#endif
	ans.clear();
	Node::setRec(x, y);
	double tmp[2] = {x, y};
	// for (int i = 0; i < MAXTREES; i++)
		// polygonTree[i].Search(Node::min, Node::max, polygonSearchCallback, tmp);
	polygonTree.Search(Node::min, Node::max, polygonSearchCallback, tmp);
#ifdef _SORT_ENABLE_
	sort(ans.begin(), ans.end());
#endif
#ifdef _TEST_PERF
	ProfilerStop();
#endif
    return ans;
}
